/// ------------------------------------------------------------------------------------------------------------------------------------
///
/// MIT License
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy
/// of this software and associated documentation files (the "Software"), to deal
/// in the Software without restriction, including without limitation the rights
/// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
/// copies of the Software, and to permit persons to whom the Software is
/// furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all
/// copies or substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
/// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
/// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
/// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
/// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
/// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
/// SOFTWARE.
///
/// Copyright (c) 2023 ycz. All rights reserved.
///
/// Created by ycz on 2023/4/23.
///
/// @file  y_treelist.c
///
/// @brief
///     y_treelist 是一种用于嵌入式设备的多叉表，可以方便用于树形数据缓存与修改
///
/// ------------------------------------------------------------------------------------------------------------------------------------



/// ------------------------------------------------------------------------------------------------------------------------------------
/// 头文件
/// ------------------------------------------------------------------------------------------------------------------------------------

#include "y_treelist.h"

#include <stdlib.h>
#include <string.h>
#include "y_sa.h"



/// ------------------------------------------------------------------------------------------------------------------------------------
/// 宏定义
/// ------------------------------------------------------------------------------------------------------------------------------------

#ifdef _Y_LL_H
#    define Y_MALLOC y_ll_malloc
#    define Y_FREE   y_ll_free
#else
#    define Y_MALLOC malloc
#    define Y_FREE   free
#endif



/// ------------------------------------------------------------------------------------------------------------------------------------
/// 结构体
/// ------------------------------------------------------------------------------------------------------------------------------------

/// @brief 多叉表节点结构体
struct treelist_node {
    uint16_t              layer;         ///< 节点层级
    uint16_t              child_num;     ///< 孩子节点数量
    uint16_t              node_num;      ///< 节点数量
    struct treelist_node *father;        ///< 父节点
    struct treelist_node *prev_brother;  ///< 上一个兄弟节点
    struct treelist_node *next_brother;  ///< 下一个兄弟节点
    struct treelist_node *child;         ///< 孩子节点
    void                 *data;          ///< 节点数据
};

/// @brief 多叉表句柄结构体
struct treelist {
    TREELIST_NODE_st *head_node;    ///< 头节点
    uint16_t          total_layer;  ///< 总层级
    uint16_t          total_node;   ///< 总节点数
};



/// ------------------------------------------------------------------------------------------------------------------------------------
/// 公有函数
/// ------------------------------------------------------------------------------------------------------------------------------------

/// @brief   打印 y_treelist 版本号
void y_treelist_print_version() {
    YLOG_VERSION("y_treelist", Y_TREELIST_MAJOR, Y_TREELIST_MINOR, Y_TREELIST_PATCH);
}

/// @brief   打印节点表
/// @param   [in] treelist                 多叉表句柄
void y_treelist_print_node_table(TREELIST_st *treelist) {

    // 断言
    if (treelist == NULL) {
        YLOGE("treelist is NULL");
        return;
    }

    // 遍历 (先序遍历)
    printf("\r\n__________________ treelist table __________________\r\n");
    printf("total_node   :  %d\r\n", treelist->total_node);
    printf("total_layer  :  %d\r\n", treelist->total_layer);
    TREELIST_NODE_st *tmp_node = treelist->head_node;  // 开始节点
    while (tmp_node) {
        printf("[" MAC_FORMAT " : %d %d %d]\r\n", MAC_TO_STR(((uint8_t *) tmp_node->data)), tmp_node->layer, tmp_node->child_num, tmp_node->node_num);  // 打印节点信息
        tmp_node = y_treelist_traverse_next(treelist, treelist->head_node, tmp_node);  // 获取下一个遍历的节点
    }
    printf("____________________________________________________\r\n");
}

/// @brief   获取节点总层级
/// @param   [in] linklist                 多叉表句柄
/// @return  节点总数量
uint16_t y_treelist_get_layer(TREELIST_st *treelist) {

    // 断言
    if (treelist == NULL) {
        YLOGE("treelist is NULL");
        return 0;
    }

    return treelist->total_layer;
}

/// @brief   获取节点总数量
/// @param   [in] linklist                 多叉表句柄
/// @return  节点总数量
uint16_t y_treelist_get_num(TREELIST_st *treelist) {

    // 断言
    if (treelist == NULL) {
        YLOGE("treelist is NULL");
        return 0;
    }

    return treelist->total_node;
}

/// @brief   获取节点当前层级
/// @param   [in] node                     节点
/// @return  孩子节点数量
uint16_t y_treelist_get_node_layer(TREELIST_NODE_st *node) {
    // 断言
    if (node == NULL) {
        YLOGE("node is NULL");
        return 0;
    }

    return node->layer;
}

/// @brief   获取孩子节点数量
/// @param   [in] node                     孩子节点
/// @return  孩子节点数量
uint16_t y_treelist_get_child_num(TREELIST_NODE_st *node) {

    // 断言
    if (node == NULL) {
        YLOGE("node is NULL");
        return 0;
    }

    return node->child_num;
}

/// @brief   判断两个节点是否为父子关系
/// @param   [in] father                   父节点
/// @param   [in] child                    子节点
/// @retval  true                          成功
/// @retval  false                         失败
bool y_treelist_is_child(TREELIST_NODE_st *father, TREELIST_NODE_st *child) {

    // 断言
    if (father == NULL || child == NULL) {
        YLOGE("father or child is NULL");
        return false;
    }

    return (child->father == father) ? true : false;
}

/// @brief   查找一个节点的数据
/// @param   [in] node                     节点指针
/// @return  [out] node_data               节点数据指针
void *y_treelist_get_data(TREELIST_NODE_st *node) {

    // 断言
    if (node == NULL) {
        // YLOGW("node is NULL");
        return NULL;
    }

    return node->data;
}

/// @brief   获取下一个遍历节点
/// @param   [in] treelist                 多叉表句柄
/// @param   [in] root                     遍历根节点
/// @param   [in] node                     当前节点
/// @return  下一个遍历节点指针
TREELIST_NODE_st *y_treelist_traverse_next(TREELIST_st *treelist, TREELIST_NODE_st *root, TREELIST_NODE_st *node) {

    // 断言
    if (treelist == NULL || node == NULL) {
        YLOGE("treelist or node is NULL");
        return NULL;
    }

    // 更新最大层级
    if (treelist->total_layer < node->layer) {
        treelist->total_layer = node->layer;
    }

    // 查找下一节点
    if (node->child) {  // 判断是否有孩子
        node = node->child;

    } else if (node->next_brother) {  // 判断是否有兄弟
        node = node->next_brother;

    } else {  // 判断祖先是否有兄弟 (往回找)
        while (1) {
            node = node->father;
            if (node == NULL || node == root) {
                return NULL;  // 回到父节点 查找结束
            }
            if (node->next_brother) {
                node = node->next_brother;  // 某个祖先有兄弟
                break;
            }
        }
    }

    return node;
}

/// @brief   查找节点第 n 层的祖先
/// @param   [in] node                     节点指针
/// @param   [in] ancestor_layer           祖先层级
/// @return  节点数据指针
TREELIST_NODE_st *y_treelist_find_ancestor(TREELIST_NODE_st *node, uint16_t ancestor_layer) {

    // 断言
    if (node == NULL) {
        YLOGE("node is NULL");
        return NULL;
    }
    if (ancestor_layer > node->layer) {
        return NULL;
    }

    // 查找祖先
    TREELIST_NODE_st *tmp_node = node;
    for (int i = 0; i < node->layer - ancestor_layer; ++i) {
        tmp_node = tmp_node->father;
        if (tmp_node == NULL) {
            return NULL;
        }
    }

    return tmp_node;
}

/// @brief   查找索引对应的节点的数据
/// @param   [in] treelist                 多叉表句柄
/// @param   [in] index                    索引
/// @return  节点的数据
void *y_treelist_find_index_data(TREELIST_st *treelist, uint16_t index) {

    TREELIST_NODE_st *node = y_treelist_find_index(treelist, index);
    if (node) {
        return node->data;
    }

    return NULL;
}

/// @brief   查找索引对应的节点
/// @param   [in] treelist                 多叉表句柄
/// @param   [in] index                    索引
/// @return  节点指针
TREELIST_NODE_st *y_treelist_find_index(TREELIST_st *treelist, uint16_t index) {

    // 断言
    if (treelist == NULL) {
        YLOGE("treelist is NULL");
        return NULL;
    }

    // 遍历 (先序遍历)
    uint16_t          tmp_index = 0;
    TREELIST_NODE_st *tmp_node  = treelist->head_node;  // 开始节点
    while (tmp_node) {

        if (index == tmp_index) {
            return tmp_node;  // 获取索引
        }
        tmp_index++;

        tmp_node = y_treelist_traverse_next(treelist, treelist->head_node, tmp_node);  // 获取下一个遍历的节点
    }

    return NULL;
}

/// @brief   查找一个节点
/// @param   [in] treelist                 多叉表句柄
/// @param   [in] node                     要查找的节点树指针
/// @param   [in] data                     要查找的数据指针
/// @param   [in] size                     要查找的数据大小
/// @return  节点指针
TREELIST_NODE_st *y_treelist_find(TREELIST_st *treelist, TREELIST_NODE_st *node, void *data, uint16_t size) {

    // 断言
    if (treelist == NULL || data == NULL || size == 0) {
        if (data) {
            YLOGE("assert error");
        }
        return NULL;
    }

    // 遍历 (先序遍历)
    TREELIST_NODE_st *tmp_node = (node == NULL) ? treelist->head_node : node;  // 开始节点
    while (tmp_node) {

        if (memcmp(data, tmp_node->data, size) == 0) {
            return tmp_node;
        }

        tmp_node = y_treelist_traverse_next(treelist, (node == NULL) ? treelist->head_node : node, tmp_node);  // 获取下一个遍历的节点
    }

    return NULL;
}

/// @brief   添加一个节点
/// @param   [in] treelist                 多叉表句柄
/// @param   [in] father_node              父节点
/// @param   [in] data                     要添加的数据指针
/// @param   [in] size                     要添加的数据大小
/// @retval  true                          成功
/// @retval  false                         失败
bool y_treelist_add(TREELIST_st *treelist, TREELIST_NODE_st *father_node, void *data, uint16_t size) {

    // 断言
    if (treelist == NULL || data == NULL || size == 0) {
        YLOGE("assert error");
        return false;
    }

    // 创建一个多叉表节点
    TREELIST_NODE_st *child_node = (TREELIST_NODE_st *) Y_MALLOC(sizeof(TREELIST_NODE_st));
    if (child_node == NULL) {
        YLOGE("y_ll_malloc node error");
        return false;
    }
    memset(child_node, 0, sizeof(TREELIST_NODE_st));
    child_node->data = Y_MALLOC(size);
    if (child_node->data == NULL) {
        YLOGE("y_ll_malloc data error");
        Y_FREE(child_node);
        return false;
    }
    memcpy(child_node->data, data, size);

    // 判断有没有头节点
    father_node = (father_node == NULL) ? treelist->head_node : father_node;  // 父节点为 NULL 则添加到根节点上
    if (father_node) {                                                        // 有头节点

        // 孩子节点初始化
        child_node->layer          = father_node->layer + 1;
        child_node->father         = father_node;

        // 更新父节点及祖先的子节点个数信息
        TREELIST_NODE_st *tmp_node = father_node;
        for (int i = 0; i < father_node->layer; ++i) {
            tmp_node->node_num++;
            tmp_node = tmp_node->father;
        }

        // 更新父节点孩子节点指针
        if (father_node->child) {  // 父节点之前有孩子
            tmp_node = father_node->child;
            for (int i = 0; i < father_node->child_num; ++i) {
                if (tmp_node->next_brother) {
                    tmp_node = tmp_node->next_brother;
                } else {
                    tmp_node->next_brother   = child_node;
                    child_node->prev_brother = tmp_node;
                }
            }
        } else {  // 父节点之前没有孩子
            father_node->child = child_node;
        }
        father_node->child_num++;

    } else {  // 没有头节点
        treelist->head_node = child_node;
        child_node->layer   = 1;
    }

    // 更新多叉表信息
    if (child_node->layer > treelist->total_layer) {
        treelist->total_layer = child_node->layer;  // 更新最大层级
    }
    treelist->total_node++;  // 总数加 1

    y_treelist_print_node_table(treelist);  // todo：注释

    return true;
}

/// @brief   删除节点及其子节点
/// @param   [in] treelist                 多叉表句柄
/// @param   [in] node                     要删除的节点
/// @param   [in] delete_cb                删除回调
/// @retval  true                          成功
/// @retval  false                         失败
bool y_treelist_delete(TREELIST_st *treelist, TREELIST_NODE_st *node, delete_cb_fun delete_cb) {

    // 断言
    if (treelist == NULL || treelist->total_node == 0) {
        YLOGE("assert error");
        return false;
    }

    // 判断删除节点类型   更新父节点及祖先的子节点个数信息
    TREELIST_NODE_st *delete_node = (node == NULL) ? treelist->head_node : node;
    TREELIST_NODE_st *father_node = delete_node->father;
    if (father_node) {  // 删除普通节点

        TREELIST_NODE_st *tmp_node = father_node;
        for (int i = 0; i < father_node->layer; ++i) {
            tmp_node->node_num -= (delete_node->node_num + 1);
            tmp_node = tmp_node->father;
        }
        father_node->child_num--;
        treelist->total_node -= (delete_node->node_num + 1);

    } else {  // 删除根节点
        treelist->head_node   = NULL;
        treelist->total_node  = 0;
        treelist->total_layer = 0;
    }

    // 遍历 (先序遍历)
    TREELIST_NODE_st *root     = delete_node;
    TREELIST_NODE_st *tmp_node = delete_node;
    while (tmp_node) {

        // YLOGD("find delete_node " MAC_FORMAT, MAC_TO_STR(((uint8_t *) tmp_node->data)));  // todo：注释

        delete_node = tmp_node;
        if (delete_node->child == NULL) {  // 叶子节点 开始删除

            // 设置下一个遍历的节点
            if (delete_node->father) {
                // 判断当前节点是不是父节点的第一个孩子
                if (delete_node->father->child == tmp_node) {
                    delete_node->father->child = delete_node->next_brother;  // 改变父亲的第一个孩子节点
                }
                if (delete_node->prev_brother) {
                    delete_node->prev_brother->next_brother = delete_node->next_brother;
                }
                if (delete_node->next_brother) {
                    delete_node->next_brother->prev_brother = delete_node->prev_brother;
                }
            }
            tmp_node = delete_node->father;  // 获取下一个遍历的节点

            // 删除节点中的数据  (保证节点数据中没有其他指针 导致内存泄露)
            // YLOGD("delete_node " MAC_FORMAT, MAC_TO_STR(((uint8_t *) delete_node->data)));  // todo：注释
            if (delete_node->data) {
                if (delete_cb) {
                    delete_cb(delete_node->data);
                } else {
                    Y_FREE(delete_node->data);
                }
                delete_node->data = NULL;
            }
            // 删除节点
            Y_FREE(delete_node);
            delete_node = NULL;

            if (tmp_node == father_node || tmp_node == NULL) {
                break;  // 删除结束 出口
            }

        } else {
            tmp_node = y_treelist_traverse_next(treelist, root, tmp_node);  // 获取下一个遍历的节点
        }
    }

    // 遍历剩下的节点 更新最大层级
    treelist->total_layer = 0;                    // 置为 0,方便遍历刷新层级
    tmp_node              = treelist->head_node;  // 开始节点
    while (tmp_node) {
        tmp_node = y_treelist_traverse_next(treelist, treelist->head_node, tmp_node);  // 获取下一个遍历的节点
    }

    y_treelist_print_node_table(treelist);  // todo：注释

    return true;
}

/// @brief   删除所有节点
/// @param   [in] treelist                 多叉表句柄
/// @param   [in] delete_cb                删除回调
/// @retval  true                          成功
/// @retval  false                         失败
bool y_treelist_clear(TREELIST_st *treelist, delete_cb_fun delete_cb) {

    // 断言
    if (treelist == NULL) {
        YLOGE("treelist is NULL");
        return false;
    }

    // 删除所有节点
    return y_treelist_delete(treelist, treelist->head_node, delete_cb);
}

/// @brief   销毁一个多叉表
/// @param   [in] treelist                 多叉表句柄
/// @param   [in] delete_cb                删除回调
/// @retval  true                          成功
/// @retval  false                         失败
bool y_treelist_destroy(TREELIST_st *treelist, delete_cb_fun delete_cb) {

    // 断言
    if (treelist == NULL) {
        YLOGW("treelist is NULL, no need destroy");
        return false;
    }

    // 删除所有节点
    y_treelist_clear(treelist, delete_cb);
    Y_FREE(treelist);

    YLOGV("treelist %p destroy succeed", treelist);

    treelist = NULL;
    return true;
}

/// @brief   创建一个多叉表
/// @return  多叉表句柄指针
TREELIST_st *y_treelist_create() {

    // 创建 treelist 句柄
    TREELIST_st *treelist = (TREELIST_st *) Y_MALLOC(sizeof(TREELIST_st));  // 开辟 结构体句柄 所需要的空间;
    if (treelist == NULL) {
        YLOGE("y_ll_malloc TREELIST_st error");
        return NULL;
    } else {
        memset(treelist, 0, sizeof(TREELIST_st));  // 清零
    }

    // 初始化
    treelist->head_node   = NULL;
    treelist->total_layer = 0;
    treelist->total_node  = 0;

    YLOGV("treelist %p create succeed", treelist);
    return treelist;
}
